import re
from fractions import Fraction as StdFraction
import math

class Fraction:
    def __init__(self, value=None):
        if value:
            std_fraction = StdFraction(value).limit_denominator()
            self.n = std_fraction.numerator
            self.d = std_fraction.denominator
        else:
            self.n=0
            self.d=1
        self.is_i = False

    def minus(self):
           return self.n < 0

    def to_float(self):
        return self.n / self.d

    def __eq__(self,other):
        return self.n == other.n and self.d == other.d

    def __add__(self,other):
       
        new_n = self.n * other.d + other.n * self.d
        new_d = self.d * other.d
        # 简化分数
        simplified_fraction = StdFraction(new_n, new_d)
        result = Fraction()
        result.n = simplified_fraction.numerator
        result.d = simplified_fraction.denominator
        return result
    
    def __sub__(self,other):
        new_n = self.n * other.d - other.n * self.d
        new_d = self.d * other.d
        # 简化分数
        simplified_fraction = StdFraction(new_n, new_d)
        result = Fraction()
        result.n = simplified_fraction.numerator
        result.d = simplified_fraction.denominator
        return result

    def __truediv__(self, two=2):
        new_n = self.n
        new_d = self.d*two
        simplified_fraction = StdFraction(new_n, new_d)
        result = Fraction()
        result.n = simplified_fraction.numerator
        result.d = simplified_fraction.denominator
        return result
    
    def __str__(self):
        if self.d == 1 and abs(self.n) !=1:
            return str(abs(self.n))
        elif self.d == 1 and abs(self.n) == 1 and self.is_i:
            return ''
        elif self.d == 1:
            return f"{abs(self.n)}"
        
        return f"{abs(self.n)}/{self.d}"

class Complex:
    def __init__(self,real=None,i=None):
        self.real = real
        self.i = i
        self.i.is_i = True
    
    def __add__(self, other):
        # 加法操作：(a + bi) + (c + di) = (a + c) + (b + d)i
        new_real = self.real+other.real
        new_i = self.i+other.i

        return Complex(new_real,new_i)

    def __sub__(self, other):
        new_real = self.real-other.real
        new_i = self.i-other.i
        return Complex(new_real,new_i)
    
    def __eq__(self,other):
        return self.real == other.real and self.i==other.i

    def __lt__(self,other):
        a = self.real.to_float() - other.real.to_float()
        b = self.i.to_float() - other.i.to_float()
        
        return  a + math.sqrt(2)*b < 0
    
    def __gt__(self,other):
        a = self.real.to_float() - other.real.to_float()
        b = self.i.to_float() - other.i.to_float()
        
        return  a + math.sqrt(2)*b > 0

    def __str__(self):
        # print("rear=%s,i=%s"%(self.real,self.i))

        if self.i.n == 0:
            return ('-' if self.real.minus() else '') + f"{self.real}"
        

        if self.real.n == 0 and self.i.d > 1:
            return f"({('-' if self.i.minus() else '') + str(self.i)})√2"
        if self.real.n == 0:
            return ('-' if self.i.minus() else '') + f"{self.i}√2"
        if self.real.n == 0:
            return ('-' if self.i.minus() else '') + f"{self.i}√2"

        
        # 正数，且有分母
        if not self.i.minus() and self.i.d > 1:
            return ('-' if self.real.minus() else '') + f"{self.real} + ({self.i})√2"
        
        # 正数，无分母
        elif not self.i.minus():
            return ('-' if self.real.minus() else '') + f"{self.real} + {self.i}√2"    
        #负数，有分母
        elif self.i.minus() and self.i.d > 1:
            return ('-' if self.real.minus() else '') + f"{self.real} - ({self.i})√2"
        #负数，无分母
        elif self.i.minus():
            return ('-' if self.real.minus() else '') + f"{self.real} - {self.i}√2"
        


class Vertex:
    def transform(self,coord_str):
        # 分割整数部分和 sqrt(2) 部分
        a_part_match =  re.search(r'[\+|-]?[0-9]*\.?[0-9]*[\+|-]', coord_str)

        a_part = a_part_match.group()[0:-1] if a_part_match else ''
        if a_part:
            # 提取 b_part（剩余部分）
            b_part = coord_str.replace(a_part, '', 1).strip()
        elif 'sqrt(2)' in coord_str:
            a_part = '0'
            b_part = coord_str
        else:
            a_part = coord_str
            b_part='0'

        # 解析 sqrt(2) 部分
        if 'sqrt(2)' in b_part:
            b_part = b_part.replace(' ', '').strip()
            b_part = b_part.replace('*', '').strip()
            b_part = b_part.replace('sqrt(2)', '').strip()

            if 1 >= len(b_part):
                b_part+='1'

        else:
            b_part = '0'

        # print("a=%s,b=%s"%(a_part,b_part))        
        return Complex(Fraction(a_part),Fraction(b_part))

    def __init__(self, str):
        str = str.replace(' ', '').strip()
        coord_str = str.split('},{',2)

        # print(coord_str)
        self.x = self.transform(coord_str[0])
        self.y = self.transform(coord_str[1])
        
    def __lt__(self,other):
        # y越大越靠上方
        if self.y > other.y:
            return True
        elif self.y == other.y and self.x < other.x:
            return True
        else:
            return False
    
    def __add__(self,other):
        result = Vertex
        x = self.x + other.x
        y = self.y + other.y
        result.x = x
        result.y = y
        return result
    
    def __sub__(self,other):
        result = Vertex
        x = self.x - other.x
        y = self.y - other.y
        result.x = x
        result.y = y
        return result
    
    def __eq__(self,other):
        return self.x == other.x and self.y == other.y

    def rotate_45(self):
        # 45度旋转
        a = self.x.real
        b = self.x.i

        c = self.y.real
        d = self.y.i

        self.x = Complex(b-d, (a-c)/2)
        self.y = Complex(b+d, (a+c)/2)
       

    def __str__(self):
        return f"({self.x}, {self.y})" 

class Piece:
    def __init__(self, anchor):
        self.anchor = anchor
        self.name = 'piece'
        # 默认顶点关系
        self.vertices = []
        # 更新顶点列表
        self.update_vertices()
        self.xfliped=False
        for v in self.vertices:
            print(v)

    def update_vertices(self):
        # 计算并更新顶点列表
        for vertex in self.vertices:
            # 假设 Vertex 类有一个方法 add，用于将两个顶点相加
            vertex.x = self.anchor.x + vertex.x
            vertex.y = self.anchor.y + vertex.y

    def xflip(self):
        #关于锚点，左右翻转
        for i in range(len(self.vertices)):
            self.vertices[i].x = self.anchor.x + self.anchor.x - self.vertices[i].x
        self.xfliped=True

    def rotate_around_anchor(self, angle):
        # 将顶点平移到原点
        for i in range(len(self.vertices)):
            self.vertices[i].x -= self.anchor.x
            self.vertices[i].y -= self.anchor.y

       
        for vertex in self.vertices:
            # 旋转每个顶点
            for _ in range(angle // 45):
                vertex.rotate_45()

        # 将顶点平移回原位置
        for i in range(len(self.vertices)):
            self.vertices[i].x += self.anchor.x
            self.vertices[i].y += self.anchor.y

    def get_min(self):
        # 找到最小的顶点
        min_vertex = min(self.vertices)
        return min_vertex
    
    def get_second_min(self):
        # 找到第二个最小的顶点
        sorted_vertices = sorted(self.vertices)
        return sorted_vertices[1] if len(sorted_vertices) > 1 else None
    
    def __lt__(self,other):
        min1 = self.get_min()
        min2 = other.get_min()
        #需要考虑min顶点重合的情况，这时候要比较第二min的顶点
        if min1 == min2:
            min1 = self.get_second_min()
            min2 = other.get_second_min()

        # 注意这里是 topmost 规则, y轴方向向上
        if min1.y > min2.y:
            return True
        elif min1.y == min2.y and min1.x < min2.x:
            return True
        else:
            return False
        

    def __str__(self):

        if self.xfliped:
            # 翻转后，确保顶点按顺时针顺序排列
            self.vertices.reverse()

        # 找到最小的顶点
        min_vertex = min(self.vertices)
        min_index = self.vertices.index(min_vertex)
        # 从最小的顶点开始重新排列顶点列表
        sorted_vertices = self.vertices[min_index:] + self.vertices[:min_index]
    
        # 返回字符串表示，不包含单引号
        return f"{self.name:15}: [{', '.join(str(v) for v in sorted_vertices)}]"

class LargeTri(Piece):
    def __init__(self, anchor):
        super().__init__(anchor)
        self.name = 'Large triangle'
        self.vertices = [
            Vertex("0},{0"),
            Vertex("2},{2"),
            Vertex("2},{0")
        ]
        self.update_vertices()

class SmallTri(Piece):
    def __init__(self, anchor):
        super().__init__(anchor)
        self.name = 'Small triangle'
        self.vertices = [
            Vertex("0},{0"),
            Vertex("1},{1"),
            Vertex("1},{0")
        ]
        self.update_vertices()

class MedTri(Piece):
    def __init__(self, anchor):
        super().__init__(anchor)
        self.name = 'Medium triangle'
        self.vertices = [
            Vertex("0},{0"),
            Vertex("1},{1"),
            Vertex("2},{0")
        ]
        self.update_vertices()

class Square(Piece):
    def __init__(self, anchor):
        super().__init__(anchor)
        self.name = 'Square'
        self.vertices = [
            Vertex("0},{0"),
            Vertex("0},{1"),
            Vertex("1},{1"),
            Vertex("1},{0")
        ]
        self.update_vertices()

class Para(Piece):
    def __init__(self, anchor):
        super().__init__(anchor)
        self.name = 'Parallelogram'
        self.vertices = [
            Vertex("0},{0"),
            Vertex("1},{1"),
            Vertex("2},{1"),
            Vertex("1},{0")
        ]
        self.update_vertices()



class TangramPuzzle:
    def __init__(self, filename):
        self.filename = filename
        self.transformations = self.parse_transformations()
        self.vertices = self.parse_vertices()

    def parse_transformations(self):
        transformations = {}
        piece_names = {
            'TangGrandTri': 'Large triangle',
            'TangMoyTri': 'Medium triangle',
            'TangPetTri': 'Small triangle',
            'TangCar': 'Square',
            'TangPara': 'Parallelogram'
        }
        piece_count = {
            'Large triangle': 0,
            'Small triangle': 0
        }

        with open(self.filename, 'r') as file:
            for line in file:
                # Check if the line contains \PieceTangram
                if '\\PieceTangram' in line:
                    # Extract PieceName
                    piece_match = re.search(r'{Tang\w+}', line)
                    # print(piece_match.group()[1:-1])
                    if piece_match:
                        piece_type = piece_match.group()[1:-1]
                        if piece_type in piece_names:
                            if piece_type == 'TangGrandTri':
                                piece_name = f'Large triangle {piece_count["Large triangle"] + 1}'
                                piece_count["Large triangle"] += 1
                            elif piece_type == 'TangPetTri':
                                piece_name = f'Small triangle {piece_count["Small triangle"] + 1}'
                                piece_count["Small triangle"] += 1
                            else:
                                piece_name = piece_names[piece_type]

                            # Extract rotate
                            rotate_match = re.search(r'rotate\s*=\s*([-\d]+)', line)
                            if rotate_match:
                                rotate = int(rotate_match.group(1))
                            else:
                                rotate = 0  # Default value

                            # Extract xscale
                            xflip_match = re.search(r'xscale\s*=\s*([-\d]+)', line)
                            yflip_match = re.search(r'yscale\s*=\s*([-\d]+)', line)
                            # print("xflip=%s,yflip=%s"%(xflip_match,yflip_match))

                            if xflip_match and not yflip_match:
                                xflip = True
                            elif xflip_match and yflip_match:
                                rotate+=180
                                xflip=False
                            else:
                                xflip = False  # Default value

                            while rotate < 0:
                                    rotate += 360
                            while rotate >= 360:
                                rotate -= 360
                            transformations[piece_name] = {'rotate': rotate, 'xflip': xflip}

        return transformations

    def parse_vertices(self):
        vertices = {}
        piece_names = {
            'TangGrandTri': 'Large triangle',
            'TangMoyTri': 'Medium triangle',
            'TangPetTri': 'Small triangle',
            'TangCar': 'Square',
            'TangPara': 'Parallelogram'
        }
        piece_count = {
            'Large triangle': 0,
            'Small triangle': 0
        }
        with open(self.filename, 'r') as file:
            for line in file:
                if '\\PieceTangram' in line:
                    piece_match = re.search(r'{Tang\w+}', line)
                    if piece_match:
                        piece_type = piece_match.group()[1:-1]
                        if piece_type in piece_names:
                            if piece_type == 'TangGrandTri':
                                piece_name = f'Large triangle {piece_count["Large triangle"] + 1}'
                                piece_count["Large triangle"] += 1
                            elif piece_type == 'TangPetTri':
                                piece_name = f'Small triangle {piece_count["Small triangle"] + 1}'
                                piece_count["Small triangle"] += 1
                            else:
                                piece_name = piece_names[piece_type]

                            anchor_match = re.search(r'\(.*\)', line)
                            if anchor_match:
                                anchor_coord = anchor_match.group()[2:-2]
                                v = Vertex(anchor_coord)
                                vertices[piece_name] = v


        return vertices

    def __str__(self):
        piece_names = {
            'Large triangle 1':'Large triangle',
            'Large triangle 2':'Large triangle',
            'Medium triangle':'Medium triangle',
            'Small triangle 1':'Small triangle',
            'Small triangle 2':'Small triangle',
            'Square':'Square',
            'Parallelogram':'Parallelogram'
        }
        output=[]
        pieces = []
        for n in piece_names:
            if self.vertices[n]:
                piece_name = piece_names[n]
                anchor = self.vertices[n]
                if 'Large triangle' in piece_name:
                    t = LargeTri(anchor)
                if 'Small triangle' in piece_name:
                    t = SmallTri(anchor)
                if 'Medium triangle' in piece_name:
                    t = MedTri(anchor)
                if 'Square' in piece_name:
                    t = Square(anchor)
                if 'Parallelogram' in piece_name:
                    t = Para(anchor)

                # 提取 rotate 值
                angle = self.transformations[n]['rotate']
                t.rotate_around_anchor(angle)

                #提取xflip
                xflip = self.transformations[n]['xflip']
                if xflip:
                    t.xflip()

                pieces.append(t)

        # 对pieces的对象进行排序
        # 对 pieces 列表进行排序
        pieces.sort()  # 使用 __lt__ 方法进行排序

        # 将 pieces 中的每个对象转换为字符串
        pieces_str = [str(piece) for piece in pieces]

        # 使用 join 方法将字符串列表连接起来
        return '\n'.join(pieces_str)

# Example usage
if __name__ == "__main__":
    T = TangramPuzzle('kangaroo.tex')
    for piece in T.transformations: 
        print(f'{piece:16}', T.transformations[piece], sep=': ')

    T = TangramPuzzle('cat.tex')
    for piece in T.transformations: 
        print(f'{piece:16}', T.transformations[piece], sep=': ')

    T = TangramPuzzle('goose.tex')
    for piece in T.transformations: 
        print(f'{piece:16}', T.transformations[piece], sep=': ')

    T = TangramPuzzle('kangaroo.tex')
    print(T)

    T = TangramPuzzle('cat.tex')
    print(T)

    T = TangramPuzzle('goose.tex')
    print(T)
    